public class Solution53 {
    public int maxSubArray(int[] nums) {
        int max=nums[0];
        int[] f=new int[nums.length];
        f[0]=nums[0];
        for (int i=1;i<nums.length;i++){
            f[i]=Math.max(f[i-1]+nums[i],nums[i]);
            max=Math.max(max,f[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new Solution53().maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
